package algorithm.leetcode.I401to600;


import java.util.Stack;

/**
 * 做法:遍历元素,试探每个元素是否为1,用单调栈保存2,再用一个变量保存3
 * 从尾向头遍历
 */

public class Q456 {

    public boolean find132pattern(int[] nums) {
        boolean result = false;

        if (nums.length < 3) return result;

        Stack<Integer> candidates2 = new Stack<>();
        candidates2.push(nums[nums.length-1]);
        int max3 = Integer.MIN_VALUE;
        for (int i = nums.length - 2; i >= 0; i--) {
            // 如果找到的3和1满足1<3就结束
            if (nums[i] < max3) return true;

            // 不然的话,将本次遍历到的1放到单调栈中去,并更新max3
            // 本来max3应该是 Math.max(max3, candidates2.pop())
            // 但是candidates2是一个自下而上递减的栈,这步操作是截断上面严格比nums[i]小的元素,所以可以简单写成candidates2.pop()
            while (!candidates2.isEmpty() && candidates2.peek() < nums[i]) {
                max3 = candidates2.pop();
            }
            // 这里不用担心nums[i]比stack顶部元素大,因为在上面的while循环已经排除了这种情况
            // if (nums[i] > max3) candidates2.push(nums[i]);  // 这里其实是下面一行的优化版本,这样stack在pop的时候可以少pop一点
            candidates2.push(nums[i]); // 这样写好理解一点
        }

        return result;
    }


    public static void main(String[] args) {
        Q456 q456 = new Q456();
        System.out.println(q456.find132pattern(new int[]{1,0,1,4,3,1,3,4,2,1,3}));
    }
}
